/* UNIVERSIDADE FEDERAL DE CAMPINA GRANDE - UFCG
 * Disciplina: Laboratorio de Estrutura de Dados
 * Professor: Marco Aurelio Spohn
 * Alunos: Alexandre Sales Vasconcelos       Mat.: 20621146
 * Atividade 7
 */

/**
 * Classe que implementa uma AVL
 *
 * @version 1.0 2008/06/13
 * @author Alexandre Sales Vasconcelos
 * @see <a href="http://lab.eda.ufcg.googlepages.com/avltree"> Atividade 7 Problema 1 </a>
 */

public class AVL {
	
	Node root = new Node();

	/**
	 * Construtor sem parametros da AVL
	 */
	public AVL() {
	}
	/**
	 * Metodo que insere nos na arvore AVL
	 * 
	 * @param string com uma sequencia de int a ser inserido na AVL
	 */
	public void insereNodosNaArvore(String string) {
		String[] vetorEntradaStr = string.split(" ");
		for (int i=0; i<vetorEntradaStr.length; i++) {
			Node newNode = new Node(Integer.parseInt(vetorEntradaStr[i]));
			addNodeAVL(root, newNode);
			Node testNode = testAVL(newNode);
			if ( testNode != null) {
				arrangesAVL(testNode);
			}
		}
	}

	/**
	 * Metodo que adciona um no na AVL
	 * 
	 * @param root raiz da AVL
	 * @param node no a ser adcionado
	 */
	private void addNodeAVL(Node root, Node node) {
		Node y = null;
		Node x = root.getFather();
		while (x!=null) {
			y = x;
			if (node.getKey()<x.getKey()) {
				x = x.getLeft();
			} else {
				x = x.getRight();
			}
		}
		node.setFather(y);
		if (y==null) {
			root.setFather(node);
		} else {
			if (node.getKey()<y.getKey()) {
				y.setLeft(node);
			} else {
				y.setRight(node);
			}
		}
	}
		
	/**
	 * Metodo que testa a integridade da AVL
	 * 
	 * @param node no que foi inserido a ser verificado se desbalanceou a AVL
	 * @return o no onde esta desbalanceado a AVL
	 */
	private Node testAVL(Node node) {
		Node answer = null;
		while (node!=null) {
			if (Math.abs(balancing(node))>=2) {
				answer = node;
				break;
			} else {
				node = node.getFather();
			}
		}
		return answer;
	}

	/**
	 * Metodo que re-arranja a AVL para que ela fique novamente balanceada
	 * 
	 * @param test no onde foi verificado o desbalanceamento
	 */
	private void arrangesAVL(Node test) {
		if (balancing(test) > 1) {
			if (balancing(test.getLeft()) > 0) {
				rotationRight(test);
			} else {
				rotationLeft(test.getLeft());
				rotationRight(test);
			}
		} else if (balancing(test) < -1) {
			if (balancing(test.getRight()) < 0) {
				rotationLeft(test);
			} else {
				rotationRight(test.getRight());
				rotationLeft(test);
			}
		}
	}
	
	/**
	 * Metodo que verificado o balanceamento da AVL
	 * 
	 * @param node no onde sera verificado se esta balanceado
	 * @return um int com o valor do balanceamento
	 */
	private int balancing(Node node) {
		int heightLeft;
		int heightRight;
		if (node.getLeft()==null) {
			heightLeft = 0;
		} else {
			heightLeft = height(node.getLeft());
		}
		if (node.getRight()==null) {
			heightRight = 0;
		} else {
			heightRight = height(node.getRight());
		}
		return heightLeft - heightRight;
	}

	/**
	 * Metodo que rotaciona o no a esquerda
	 * 
	 * @param node no a ser rotacionado
	 */
	private void rotationLeft(Node node) {
		Node y = node.getRight();
		Node a = node.getLeft();
		Node b = y.getLeft();
		Node c = y.getRight();
		int info = node.getKey();
		node.setKey(y.getKey());
		y.setKey(info);
		node.setRight(c);
		if (c != null)
			c.setFather(node);
		node.setLeft(y);
		y.setFather(node);
		y.setLeft(a);
		if (a != null)
			a.setFather(y);
		y.setRight(b);
		if (b != null)
			b.setFather(y);
	}
	
	/**
	 * Metodo que rotaciona o no a direita
	 * 
	 * @param node no a ser rotacionado
	 */
	private void rotationRight(Node node) {
		Node y = node.getLeft();
		Node a = y.getLeft();
		Node b = y.getRight();
		Node c = node.getRight();
		int info = node.getKey();
		node.setKey(y.getKey());
		y.setKey(info);
		node.setLeft(a);
		if (a != null)
			a.setFather(node);
		node.setRight(y);
		y.setFather(node);
		y.setLeft(b);
		if (b != null)
			b.setFather(y);
		y.setRight(c);
		if (c != null)
			c.setFather(y);
	}

	/**
	 * Metodo que mede a altura do no
	 * 
	 * @param node no a ser medido sua altura
	 * @return int com a altura do no
	 */
	private int height(Node node) {
		int height = 1;
		if (node.getLeft() != null)
			height = 1 + height(node.getLeft());
		if (node.getRight() != null)
			height = Math.max(1 + height(node.getRight()), height);
		return height;
	}

	/**
	 * Metodo que retorna a posicao em um array ordenado por nivel
	 * 
	 * @param root no raiz da AVL
	 * @return int com a posicao do no na array ordenada por nivel
	 */
	private int index(Node root) {
		if (root.getFather()==null) {
			return 0;
		} else {
			if (root.getFather().getLeft()==root) {
				return index(root.getFather()) * 2 + 1;
			} else {
				return index(root.getFather()) * 2 + 2;
			}
		}
	}

	/**
	 * Metodo que pecorre a AVL em ordem
	 * 
	 * @param treeAVL arvore AVL a ser percorrida em ordem 
	 * @param raiz no a ser percorrido
	 */
	private void walkInOrder(Integer[] treeAVL, Node raiz) {
		if (raiz != null) {
			walkInOrder(treeAVL, raiz.getLeft());
			treeAVL[index(raiz)] = raiz.getKey();
			walkInOrder(treeAVL, raiz.getRight());
		}
	}

	/**
	 * Metodo que retorna uma String formatada, nesta caso, uma lista ordenada por nivel.
	 * 
	 * @return uma String formatada
	 */
	public String toString() {
		Integer[] listInLevel = new Integer[(int) Math.pow(2, height(root.getFather()))];
		for(int i=height(root);i>0;i--)
			 walkInOrder(listInLevel, root.getFather());
		String answer = "";
		for (int j = 0; j < listInLevel.length; j++) {
			if(listInLevel[j]!=null){
				answer+=listInLevel[j].toString()+" ";
			}
		}
		return answer.trim();
	}

}
